package leetcode.median;

public class $375_GetMoneyAmount {

    static int[][] dp = new int[210][210];

    public int getMoneyAmount(int n) {
        return dfs(1, n);
    }

    public int dfs(int left, int right) {
        if (left >= right) {
            return 0;
        }
        if (dp[left][right] != 0) {
            return dp[left][right];
        }
        int res = Integer.MAX_VALUE;
        for (int x = left; x <= right; x++) {
            int cur = Math.max(dfs(left, x - 1), dfs(x + 1, right)) + x;
            res = Math.min(cur, res);
        }
        dp[left][right] = res;
        return res;
    }
}
